package com.xw.class10;

/**
 * @author: xw
 * @create: 2023/6/7 9:29
 * @description:返回两个链表的入环节点
 */
public class Code01_FindFirstCircleNode {

    static class Node {
        public int value;
        public Node next;

        public Node(int value){
            this.value = value;
        }
    }

    /**
     *  如果链表存在换，那么返回入环节点 ，如果不存在环，返回相交的节点 ，不想交返回null
     * @return
     */
    public static Node getFirstCircleNode(Node head1,Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        Node loop1 = getLoopNode(head1);
        Node loop2 = getLoopNode(head2);
        if(loop1 == null && loop2 == null){
            return exitNoLoop(head1,head2);
        }
        if(loop1 != null && loop2 != null) {
            return bothLoop(head1,loop1,head2,loop2);
        }
        return null;

    }

    /**
     * 找到链表入环的第一个节点，如果不存在返回 null
     *
     *  使用缓慢指针发，快指针一次移动两个节点  慢指针一次移动一个节点  当快指针再次赶上慢指针时，
     *  快指针回到头结点，并且一次移动一个节点，再次和慢指针相遇时即为链表的入环节点
     * @param head
     * @return
     */
    public static Node getLoopNode(Node head){
        if(null == head || head.next == null || head.next.next == null){
            return null;
        }

        Node slow = head.next;
        Node fast = head.next.next;
        while(slow != fast){
            if(fast.next == null || fast.next.next == null){
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        //如果走到此处，说明有环，重置快指针
        fast = head;
        while (slow != fast){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     *  如果链表无环 ，判断是否有相交的节点，如果有返回相交节点，无则返回null
     * @param head1
     * @param head2
     * @return
     */
    public static Node exitNoLoop(Node head1, Node head2) {
        Node cur1 = head1;
        Node cur2 = head2;
        int n  = 0;
        while (cur1.next != null){
            n++;
            cur1 = cur1.next;
        }
        while (cur2.next != null){
            n--;
            cur2 = cur2.next;
        }
        if(cur1 != cur2){
            return null;
        }
        //谁长谁变成cur1
        cur1 = n > 0 ? head1 : head2;
        cur2 = cur1 == head1 ? head2:head1;
        n = Math.abs(n);
        //因为长链表和短链表如果要相交，那么相交的节点一定是在（长链表 - 短帘表）的长度对应的节点之后
        while (n != 0){
            n--;
            cur1 = cur1.next;
        }
        while (cur1 != cur2){
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;

    }

    /**
     * 都是有环链表 有以下三种情况
     *  第一 入环节点相等
     *  第二 入环节点不相等
     *  第三 不相交
     *
     * @param head1 头结点
     * @param loop1 入环节点
     * @param head2 头结点
     * @param loop2 入环节点
     * @return
     */
    public static Node bothLoop(Node head1, Node loop1 , Node head2, Node loop2) {
        Node cur1 = null;
        Node cur2 = null;
        if(loop1 ==loop2){
            cur1 = head1;
            cur2 = head2;
            int n = 0;
            while (cur1 != loop1){
                n++;
                cur1 = cur1.next;
            }
            while (cur2 != loop2){
                n--;
                cur2 = cur2.next;
            }
            cur1 = n > 0 ? head1 : head2;
            cur2 = cur1 == head1 ? head2 : head1;
            n = Math.abs(n);
            while (n != 0){
                n--;
                cur1 = cur1.next;
            }
            while (cur1 != cur2){
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        }else{
            cur1 = loop1.next;
            while (cur1 != loop1){
                if(cur1 == loop2){
                    return loop1;
                }
                cur1 = cur1.next;
            }
            return null;
        }
    }
}
